In computer graphics, a computer is used to generate digital data that represents the projection of surfaces of objects in, for example, a three-dimensional scene, illuminated by one or more light sources, onto a two-dimensional image plane, to simulate the recording of the scene by, for example, a camera. The camera may include a lens for projecting the image of the scene onto the image plane, or it may comprise a pinhole camera in which case no lens is,used. The two-dimensional image is in the form of an array of picture elements (which are variable termed “pixels” or “Pels”), and the digital data generated for each pixel represents the color and luminance of the scene as projected onto the image plane at the point of the respective pixel in the image plane. The surfaces of the objects may have any of a number of types of characteristics, including shape, color, specularity, texture, and so forth, which are preferably rendered in the image as closely as possible, to provide a realistic-looking image.
Typically in computer graphics, images are rendered by evaluating integrals to evaluate rays that are traced between a light source and pixels on the image plane, the rays representing paths that would be taken by photons between a respective light source and the pixels on the image plane. The evaluations of the integrals essentially provide information as to the intensity and color of the photon flux that is incident on respective pixels in the image plane. Typically, the integrals have the form
                              ∫                      I                          s              1                                      ⁢                  …          ⁢                                          ⁢                                    ∫                              I                                  s                  n                                                      ⁢                                          f                ⁡                                  (                                                            x                                              (                        1                        )                                                              ,                    …                    ⁢                                                                                  ,                                          x                                              (                        n                        )                                                                              )                                            ⁢                              ⅆ                                  x                                      (                    n                    )                                                              ⁢                                                          ⁢              …              ⁢                                                          ⁢                              ⅆ                                  x                                      (                    n                    )                                                                                                          (        1        )            where “ƒ” is a function defined on an s1+ . . . +sn=s dimensional unit cube [0,1)s. Depending on the position and orientation of the image plane with respect to the light source(s), some of the rays may represent photon paths directly from a light source to the pixel on the image plane. Similarly, depending on the position and orientation of the image plane relative to objects in the scene, some of the rays may represent photon paths from the light source to a pixel on the image plane after being reflected off one or more of the surfaces of objects in the scene. As noted above, surfaces of the objects may have any of a number of types of characteristics, which, in turn, can affect things like the colors and directions of the photons reflected therefrom. A surface's color can affect the colors of the reflected photons. For example, if the surface is blue, the reflected photons would be primarily if not exclusively photons associated with the color blue. Other characteristics of a surface can affect the directions of the photons reflected therefrom, and thus can affect the path(s) of the ray(s) traced from the respective surface. Since various types of surface characteristics may cause photons to be reflected in a number of directions, a ray that is incident on a surface is typically “split” into a plurality of reflected rays, which may have directions that depend on the characteristics of the respective surface. For example, if a surface is generally specular, the reflected rays will have similar directions, near the angle of incidence. On the other hand, if surface is generally diffuse, the reflected rays will generally have a wide variety of directions, which may differ substantially from the angle of incidence.
Typically, integrals such as that represented by equation (1) do not have closed form solutions, and are generally evaluated numerically. An integral such as that represented by equation (1) can be evaluated numerically as follows:
                                          1                          N              1                                ⁢                                    ∑                                                i                  1                                =                0                                                              N                  1                                -                1                                      ⁢                                                  ⁢                          …              ⁢                                                          ⁢                              1                                  N                  n                                            ⁢                                                ∑                                                            i                      n                                        =                    0                                                                              N                      n                                        -                    1                                                  ⁢                                  f                  ⁡                                      (                                                                  x                                                  i                          1                                                                          (                          1                          )                                                                    ,                      …                      ⁢                                                                                          ,                                              x                                                  i                          n                                                                          (                          n                          )                                                                                      )                                                                                      ,                            (        2        )            where each ƒ(xi1(1), . . . , xin(n)) in the sum is an evaluation of the function “ƒ” at a sample point (xi1(n), . . . , xin(n)) in the integration domain. Sample points can be generated using any of a number of methodologies; the Grabenstein application describes a methodology in which sample points comprise samples from s-dimensional strictly-deterministic low-discrepancy sequences such as Halton sequences, and the Keller application describes a methodology in which sample points comprise s-dimensional Hammersley point sets. Generally, ones of the dimensions s1, . . . sn are associated with respective photon traces between the light source and the image plane.
Problems can arise particularly in situations in which a number of rays have substantially similar directions.